﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions.Problems
{
    /*
     * The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

     * */
    class Problem104 : IProblem
    {
        public string Calculate()
        {
            BigInteger a = 1;
            BigInteger b = 1;

            char[] digits = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };

            long i = 2;


            long a1 = 1;
            long b1 = 1;

            long a2 = 1;
            long b2 = 1;

            while (true)
            {
                i++;
                long temp = a1;
                a1 = b1;
                b1 = temp;

                a1 = a1 + b1;
                a1 %= 1000000000;

                long temp2 = a2;
                a2 = b2;
                b2 = temp2;

                a2 = a2 + b2;

                int numDigits = CommonFunctions.NumberOfDigits(a2);

                if (numDigits > 15)
                {
                    int digitDifference = numDigits - 15;
                    a2 = a2 / (int)Math.Pow(10, digitDifference);
                    b2 = b2 / (int)Math.Pow(10, digitDifference);
                }


                if (a2 >= 123456789)
                {

                    String a1String = a1.ToString();
                    bool pandigital = true;
                    foreach (char c in digits)
                        if (!a1String.Contains(c))
                        {
                            pandigital = false;
                            break;
                        }

                    if (pandigital)
                    {
                        String a2String = a2.ToString().Substring(0, 9);
                        foreach (char c in digits)
                            if (!a2String.Contains(c))
                            {
                                pandigital = false;
                                break;
                            }

                        if (pandigital)
                            break;
                    }
                }
            }

            //while (true)
            //{
            //    a = a + b;
            //    i++;

            //    if (a >= 123456789)
            //    {
            //        String aString = a.ToString();
            //        String num = aString.Substring(0, 9);
            //        bool pandigital = true;
            //        foreach (char c in digits)
            //            if (!num.Contains(c))
            //            {
            //                pandigital = false;
            //                break;
            //            }


            //        num = aString.Substring(aString.Length - 9, 9);
            //        foreach (char c in digits)
            //            if (!num.Contains(c))
            //            {
            //                pandigital = false;
            //                break;
            //            }

            //        if (pandigital)
            //        {
            //            break;
            //        }
            //    }

            //    b = a + b;
            //    i++;

            //    if (b >= 123456789)
            //    {
            //        String bString = b.ToString();
            //        String num = bString.Substring(0, 9);
            //        bool pandigital = true;
            //        foreach (char c in digits)
            //            if (!num.Contains(c))
            //            {
            //                pandigital = false;
            //                break;
            //            }


            //        num = bString.Substring(bString.Length - 9 , 9);
            //        foreach (char c in digits)
            //            if (!num.Contains(c))
            //            {
            //                pandigital = false;
            //                break;
            //            }

            //        if (pandigital)
            //        {
            //            break;
            //        }
            //    }
            //}


            Console.Beep();
            return i.ToString();
        }
    }
}
